package com.sx.sx1.lintcode.day717;

import java.util.HashMap;
import java.util.Map;

public class LC1396 {

    static class Solution {
        /**
         * @param sets: Initial set list
         * @return: The final number of sets
         */
        public int setUnion(int[][] sets) {
            UF uf = new UF();
            for (int[] set : sets) {
                int pid = set[0];
                for (int i = 0; i < set.length; i++) {
                    uf.union(pid,set[i]);
                }
            }

            return uf.sets;
        }

        static class UF{
            public Map<Integer,Integer> parents = new HashMap<>();
            public Map<Integer,Integer> size = new HashMap<>();
            public Map<Integer,Integer> help = new HashMap<>();
            public int sets = 0;

            public int find(int x){
                if (!parents.containsKey(x)) {
                    parents.put(x,x);
                    size.put(x,1);
                    sets++;
                }

                int hi=0;
                while (x!=parents.get(x)){
                    help.put(hi++,x);
                    x = parents.get(x);
                }

                for(hi--;hi>=0;hi--){
                    parents.put(help.get(hi),x);
                }

                return x;
            }

            public void union(int a,int b){
                int f1 = find(a);
                int f2 = find(b);

                if(f1!=f2){
                    int s1 = size.get(f1);
                    int s2 = size.get(f2);
                    int s = s1+s2;
                    if(s1>=s2){
                        size.put(f1,s);
                        parents.put(f2,f1);
                    }else{
                        size.put(f2,s);
                        parents.put(f1,f2);
                    }
                    sets--;
                }
            }
        }
    }

}


/*
        LintCode-Logo
        搜索题目、标签、题集
        中文
        avatar
        您有211条未读消息，请及时查看
        1396 · 集合合并
        算法
        中等
        通过率
        51%

        题目
        题解22
        笔记
        讨论45
        排名
        记录
        描述
        有一个集合组成的list，如果有两个集合有相同的元素，将他们合并。返回最后还剩下几个集合。

        最短时间刷“透”算法面试：《66页算法宝典》.pdf

        微信添加【jiuzhangfeifei】备注【66】领取


        集合数 n <= 1000。
        每个集合的元素个数 m <= 100。
        元素一定是非负整数，且不大于 100000。
        样例
        样例1:

        输入：list = [[1,2,3],[3,9,7],[4,5,10]]
        输出：2 .
        样例：剩下[1,2,3,9,7]和[4,5,10]这2个集合。
        样例 2:

        输入：list = [[1],[1,2,3],[4],[8,7,4,5]]
        输出 ：2
        解释：剩下[1,2,3]和[4,5,7,8] 2个集合。
        相关知识
        学习《算法求职课——百题精讲》课程中的21.3集合合并-视频讲解相关内容 ，了解更多相关知识！
        标签
        企业
        Facebook
        推荐课程

        春招算法高频题冲刺班
        精准押题，抱佛脚突击算法面试，最近6个月新题/难题/高频题全覆盖！
        19/43
        已开启智能提示
        发起考试
        30 分 00 秒
        123456789
public class Solution {
    /**
     * @param sets: Initial set list
     * @return: The final number of sets

    public int setUnion(int[][] sets) {
        // Write your code here
    }
}
    控制台
            历史提交

*/
